package com.dyz.leetcode._05_sort;

import java.util.Arrays;
import java.util.Random;

public class quickSortDemo {
    public static void main(String[] args) {
        int[] arr = {19, 97, 9, 17, 20, 8};
        QuickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    public static void QuickSort(int[] arr, int left, int right){
        
        //首先要进行一个数据的校验
        if(left > right){
            return;
        }
        //设立左边标记，右边标记，基准
        int l = left;
        int r = right;
        int pivot = arr[left];
        //定义中间变量，用于交换
        int temp =0;

        while(l < r) {
            //从右往左开始找，直到找到一个小于基准的数字停下来
            //跳出循环
            while (l < r && arr[r] >= pivot) {
                r--;
            }
            //从左往右开始找，直到找到一个大于基准的数字停下来
            //跳出循环
            while (l < r && arr[l] <= pivot) {
                l++;
            }
            //找到之后，交换两边数字
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        //跳出循环
        //此时说明l=r;
        //将基准数字与l=r位置上的数字进行交换
        arr[left] = arr[l];
        arr[l] = pivot;
        //此时，大于基准的数字都在基准的右边
        //小于基准的数字都在基准的左边

        //左半边递归
        QuickSort(arr,left, l-1);
        //右半边递归
        QuickSort(arr, r+1, right);
    }
}
